package com.zwj.interview.基本运算;

import java.util.List;

/**
 * @Author: Zwj
 * @Date: 2022/3/1 11:12
 */
public class 幂运算 {
    int base = 1337;

    //计算a的k次幂与base的模运算
    public int mypow(int a, int k) {
        a %= base;
        int res = 1;
        for (int i = 0; i < k; i++) {
            res *= a;
            res %= base;
        }
        return res;
    }

    //幂指数用数组表示,计算a的nums次幂运算，比如1567次幂
    int superpow(int a, List<Integer> nums) {
        if (nums.size() == 0) {
            return 1;
        }
        //拿到指数最后一位，比如7，先计算7次幂
        int last = nums.get(nums.size() - 1);
        nums.remove(nums.size() - 1);
        int part1 = mypow(a, last);
        int part2 = mypow(superpow(a, nums), 10);
        //part1就是第一步值跟base取模  (a*b)%k=(a%K)(b%k)%k
        return (part1 * part2) % base;
    }
}